#include <ctype.h>
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include "param.h"
#include "types.h"
#include "retarder.h"

/* 增加内存压力 */
static void
swap (uint64* a, uint64* b) {
    uint64 tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

static void
shift_down (uint64* base, uint64 n, uint64 i) {
    uint64 j;
    /* L:x2+1 */
    /* R:x2+2 */
    do {
        j = i * 2;
        j++;
        if (j+1 < n) {
            if (base[j] < base[j + 1]) {
                j++;
            }
        }
        if (j >= n) break;
        if (base[i] < base[j]) {
            swap (base + i, base + j);
            i = j;
        } else {
            break;
        }
    } while (j < n);
}

static void
make_heap (uint64 *base, uint64 n) {
    uint64 i;
    i = n / 2;
    for (;;) {
        shift_down (base, n, i);
        if (i == 0) break;
        i--;
    }
}


void
heap_sort (uint64* base, uint64 n) {
    uint64 i;
    make_heap (base, n);
    for (i = n-1; i > 0; i--) {
        swap (base, base+i);
        shift_down (base, i, 0);
    }
}

static void
swap_no_cache (uint64* a, uint64* b, uint64* retarder0, uint64* retarder1) {
    RETARDER_INIT ();
    RETARDER_SWAP (*a, *b);
}

static void
shift_down_no_cache (uint64* base, uint64 n, uint64 i, uint64* retarder0, uint64* retarder1) {
    uint64 j;
    /* L:x2+1 */
    /* R:x2+2 */
    RETARDER_INIT ();
    do {
        RETARDER_ASSIGN (j, i*2);
        j++;
        if (j+1 < n) {
            if (base[j] < base[j + 1]) {
                j++;
            }
        }
        if (j >= n) break;
        if (base[i] < base[j]) {
            swap_no_cache (base + i, base + j, retarder0, retarder1);
            RETARDER_ASSIGN (i, j);
        } else {
            break;
        }
    } while (j < n);
}

static void
make_heap_no_cache (uint64 *base, uint64 n, uint64* retarder0, uint64* retarder1) {
    uint64 i;
    i = n / 2;
    for (;;) {
        shift_down_no_cache (base, n, i, retarder0, retarder1);
        if (i == 0) break;
        i--;
    }
}


void
heap_sort_no_cache (uint64* base, uint64 n, uint64* retarder0, uint64* retarder1) {
    // printf ("sorting... nocache.\n");
    uint64 i;
    make_heap_no_cache (base, n, retarder0, retarder1);
    for (i = n-1; i > 0; i--) {
        swap_no_cache (base, base+i, retarder0, retarder1);
        shift_down_no_cache (base, i, 0, retarder0, retarder1);
    }
}

int
comp (const void* a, const void* b) {
    return *(uint64*)a > *(uint64*)b;
}

void
quick_sort (uint64* base, uint64 n) {
    qsort (base, n, sizeof (uint64), comp);
}